package com.yang.Dp;

import java.util.concurrent.locks.ReentrantLock;

public class climbStairs {
}
/*
* 分析一波
* 1.确定 dp[i] 表示 第i层有多少种爬法
* 2.确定递推公式 比如dp[i] 可以由 dp[i - 1] 跨一步 或者 dp[i - 2] 跨两步 到dp[i]
*                        所以有dp[i] = dp[i - 1] + dp[i - 2]
* 3.数组如何初始化？  dp[1] = 1  dp[2] = 2
* 4.确定遍历顺序 后一个结果依靠前一个结果  所以从前往后遍历
* 5.距离推导公式 i = 5  do[5] = dp[4] + dp[3] = dp[3] + dp[2] + dp[1] + dp[2] = 8
* */
class LeetCode70Solution {
    // 自低向上的解法1
    public int climbStairs(int n) {
        if (n == 2){
            return 2;
        }
        if (n < 2){
            return 1;
        }

        int nums1 = 1;
        int nums2 = 2;
        int midNums = 0;
        for(int i = 2; i < n; i++){
            midNums = nums1 + nums2;
            nums1 = nums2;
            nums2 = midNums;
        }
        return midNums;
    }

    // 自低向上的解法2  DP
    public int climbStairs2(int n) {
        int[] dp = new int[n];
        dp[0] = 1;
        dp[1] = 1;

        for(int i = 2; i < n; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}
